package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/third-maximum-number/">
 * 414. 第三大的数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3, 2, 1]
 * 输出：1
 * 解释：第三大的数是 1 。
 * <p>
 * 示例 2：
 * <p>
 * 输入：[1, 2]
 * 输出：2
 * 解释：第三大的数不存在, 所以返回最大的数 2 。
 * <p>
 * 示例 3：
 * <p>
 * 输入：[2, 2, 3, 1]
 * 输出：1
 * 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
 * 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
 *  
 * <p>
 * 提示：
 * <ul>
 * <li>1 <= nums.length <= 104</li>
 * <li>-231 <= nums[i] <= 231 - 1</li>
 * </ul>
 * 进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
 *
 * @author or2
 * @date 2021年10月06日 时间: 8:05
 */
public class No414 {
    public int thirdMax(int[] nums) {
        int length = nums.length;
        if (length == 1)
            return nums[0];
        if (length == 2)
            return Math.max(nums[0], nums[1]);

        boolean hasBound = false;
        int[] auxiliary = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int num : nums) {
            if (!hasBound)
                if (num == Integer.MIN_VALUE)
                    hasBound = true;
            if (num > auxiliary[2]) {
                /* 去重 */
                if (num == auxiliary[0] || num == auxiliary[1])
                    continue;
                auxiliary[2] = num;
                for (int i = 2; i > 0; i--)
                    if (num > auxiliary[i - 1]) {
                        int temp = auxiliary[i - 1];
                        auxiliary[i - 1] = num;
                        auxiliary[i] = temp;
                    }
            }
        }

        System.gc();
        try {
            Thread.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        if (hasBound)
            if (auxiliary[1] == Integer.MIN_VALUE)
                return auxiliary[0];
            else
                return auxiliary[2];
        else
            return auxiliary[2] == Integer.MIN_VALUE? auxiliary[0]: auxiliary[2];
    }
}
